import copy
import time

# Name: Sudoku | 2018 - 2020
# Version: 5.0 (CLI)
# Last update: 2020
# ----------------------------------------
# Developer: Monkeyhbd | 2017 - 2020
# Email: monkeyhbd@163.com
# ----------------------------------------
#
#                         ##
#                         ##    ##    ####    ##    ##    ##      ##          ##
#     ##  ##      ####    ##  ##    ##    ##    ##  ##    ##      ##          ##
#   ##  ##  ##  ##    ##  ####      ########      ##      ####    ####      ####
#   ##  ##  ##  ##    ##  ##  ##    ##            ##      ##  ##  ##  ##  ##  ##
#   ##  ##  ##    ####    ##    ##    ####      ##        ##  ##  ####      ####
#
# ----------------------------------------
# License: GNU GPLv2

class Sudoku:
    # Example: [[1],[8],[6],[2],[7],[3,9],[9],[4],[5,9]] --> [[1],[8],[6],[2],[7],[3],[9],[4],[5]]
    def Exclusion_unit(sudoku_unit):
        while True:
            sum0 = 0
            for x in range(9):
                sum0 += len(sudoku_unit[x])

            for x in sudoku_unit:
                if len(x) == 1:
                    key = x[0]
                    for y in range(9):
                        if key in sudoku_unit[y] and len(sudoku_unit[y]) != 1:
                            sudoku_unit[y].remove(key)

            sum1 = 0
            for x in range(9):
                sum1 += len(sudoku_unit[x])

            if sum1 == sum0:
                break

        return sudoku_unit

    # Example: [[1],[8],[6],[2],[7],[3,9],[5,9],[4],[5,9]] --> [[1],[8],[6],[2],[7],[3],[5,9],[4],[5,9]]
    def Look_unit(sudoku_unit):
        else_number = []
        for p in sudoku_unit:
            if len(p) != 1:
                else_number += p
        for n in range(1,10):
            if else_number.count(n) == 1:
                for x in range(9):
                    if n in sudoku_unit[x]:
                        sudoku_unit[x] = [n]
        return sudoku_unit

    # Example: [[5, 9], [4], [5, 9], [3], [1], [7], [6], [2], [8]] --> True
    # Example: [[5, 9], [4], [5, 9], [3], [7], [7], [6], [2], [8]] --> False
    def Check_unit(sudoku_unit):
        for p in sudoku_unit:
            if len(p) == 1 and sudoku_unit.count(p) > 1:
                return False
        else:
            return True

    def Check(sudoku):
        for y in range(9):  # Check in Row.
            if not Sudoku.Check_unit(sudoku[y]):
                return False
        for x in range(9):  # Check in Column.
            if not Sudoku.Check_unit([sudoku[y][x] for y in range(9)]):
                return False
        for b in range(9):  # Check in Block.
            help_place = []
            for x in range((b % 3) * 3, (b % 3) * 3 + 3):
                for y in range(int(b / 3) * 3, int(b / 3) * 3 + 3):
                    help_place.append([x, y])
            if not Sudoku.Check_unit([sudoku[p[1]][p[0]] for p in help_place]):
                return False
        return True

    def Count(sudoku):
        c = 0
        for y in range(9):
            for x in range(9):
                c += len(sudoku[y][x])
        return c

    def Exclusion(sudoku):
        while True:
            sum0 = 0
            for x in range(9):
                for y in range(9):
                    sum0 += len(sudoku[y][x])
            
            for y in range(9):  # Exclusion and look in Raw.
                sudoku[y] = Sudoku.Exclusion_unit(sudoku[y])
                sudoku[y] = Sudoku.Look_unit(sudoku[y])

            for x in range(9):  # Exclusion and look in Column.
                help_unit = Sudoku.Exclusion_unit([sudoku[y][x] for y in range(9)])
                help_unit = Sudoku.Look_unit(help_unit)
                for y in range(9):
                    sudoku[y][x] = help_unit[y]

            for b in range(9):  # Exclusion and look in Block.
                help_place = []
                for x in range((b % 3) * 3, (b % 3) * 3 + 3):
                    for y in range(int(b / 3) * 3, int(b / 3) * 3 + 3):
                        help_place.append([x, y])
                help_unit = Sudoku.Exclusion_unit([sudoku[p[1]][p[0]] for p in help_place])
                help_unit = Sudoku.Look_unit(help_unit)
                for idx in range(9):
                    sudoku[help_place[idx][1]][help_place[idx][0]] = help_unit[idx]

            sum1 = 0
            for x in range(9):
                for y in range(9):
                    sum1 += len(sudoku[y][x])

            if sum1 == sum0:
                break
        
        return sudoku

    def Enumeration(sudoku, empty=[], idx=0, key=[]):
        if idx == 0:
            key = copy.deepcopy(sudoku)
            empty = []
            for y in range(9):
                for x in range(9):
                    if len(sudoku[y][x]) > 1:
                        empty.append([x, y])

        for n in sudoku [empty[idx][1]] [empty[idx][0]]:
            key [empty[idx][1]] [empty[idx][0]] = [n]
            if idx == len(empty) - 1:
                if Sudoku.Check(key):
                    return key
            else:
                if Sudoku.Check(key):
                    help_return = Sudoku.Enumeration(sudoku, empty, idx+1, [a.copy() for a in key])
                    if help_return != None:
                        return help_return
                    
    def Solution(sudoku):
        sudoku = Sudoku.Exclusion(sudoku)

        if Sudoku.Count(sudoku) > 81:
            sudoku = Sudoku.Enumeration(sudoku)

        return sudoku


if __name__ == '__main__':
    sudoku_data = []
    for x in range(9):
        sudoku_data.append([])
        gen = input('Line' + str(x + 1) + ': ')
        for y in range(9):
            num = int(gen[y])
            if num == 0:
                sudoku_data[x].append([n for n in range(1, 10)])
            else:
                sudoku_data[x].append([num])

    t0 = time.time()
    sudoku_data = Sudoku.Solution(sudoku_data)
    te = time.time()

    print()
    for y in range(9):
        for x in range(9):
            print(sudoku_data[y][x], end=' ')
        print()
    print()
    print('The Python program use %.5f s.'%(te-t0))
